package com.datastructure.test.rightviewoftree;

import java.util.ArrayList;
import java.util.Arrays;

public class RightViewOfTree {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] xianxu={1,2,4,5,3};
        int[] zhongxu={4,2,5,1,3};
        RightViewOfTree rightViewOfTree = new RightViewOfTree();
        int[] solve = rightViewOfTree.solve(xianxu, zhongxu);
        System.out.println(solve);
    }

    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = reConstructBinaryTree(xianxu, zhongxu);
        getLevelIterator(root,0);
        int[] data = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ArrayList<Integer> list = res.get(i);
            data[i]=list.get(list.size()-1);
        }
        return data;
    }

    public void getLevelIterator(TreeNode root,int level){
        if(res.size()==level){
            res.add(new ArrayList<>());
        }
        ArrayList<Integer> arrayList = res.get(level);
        arrayList.add(root.val);
        if(root.left!=null){
            getLevelIterator(root.left,level+1);
        }
        if(root.right!=null){
            getLevelIterator(root.right,level+1);
        }
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder){
        if(postorder.length==0||inorder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==postorder[postorder.length-1]){
                root.left=buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
                root.right=buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),Arrays.copyOfRange(postorder,i,postorder.length-1));
                break;
            }
        }
        return root;
    }
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
